//
// Created by 高森森 on 2022/2/17.
//

#ifndef LEETCODE_SOLUTION54_H
#define LEETCODE_SOLUTION54_H
#include<iostream>
#include<vector>
using namespace std;

class Solution54 {
public:
    int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) {
        int n=passingFees.size();
        vector<vector<int>>dp(maxTime+1,vector<int>(n,INT_MAX/2));
        dp[0][0]=passingFees[0];
        for(int t=1;t<=maxTime;t++){
            for(auto &edge:edges){
                int u=edge[0];
                int v=edge[1];
                int cost=edge[2];
                if(cost<=t){
                    dp[t][u]=min(dp[t-cost][v]+passingFees[u],dp[t][u]);
                    dp[t][v]=min(dp[t-cost][u]+passingFees[v],dp[t][v]);
                }
            }
        }
        int ans=INT_MAX/2;
        for(int i=1;i<=maxTime;i++){
            ans=min(ans,dp[i][n-1]);
        }
        return ans==INT_MAX/2?-1:ans;
    }
};


#endif //LEETCODE_SOLUTION54_H
